package com.peng.leetcode.tree;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * LowestCommonAncestor
 *
 * I. 二叉搜索树的最近公共祖先
 *
 * 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
 *
 * @author: lupeng6
 * @create: 2021/1/11 10:11
 */
public class LowestCommonAncestor {

    public static void main(String[] args) {
        TreeNode root = TreeMain.array2tree(new Integer[]{6, 2, 8, 0, 4, 7, 9, null, null, 3, 5});
        TreeNode p = new TreeNode(2);
        TreeNode q = new TreeNode(8);
        new LowestCommonAncestor().lowestCommonAncestor(root, p, q);
    }

    private Map<TreeNode, TreeNode> parent = new HashMap<>();

    private Set<TreeNode> set = new HashSet<>();

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        dfs(root);
        while (p != null) {
            set.add(p);
            p = parent.get(p);
        }
        while (q != null) {
            if (set.contains(q)) {
                return q;
            }
            q = parent.get(q);
        }
        return null;
    }

    private void dfs(TreeNode root) {
        if (root == null) {
            return;
        }
        if (root.left != null) {
            parent.put(root.left, root);
            dfs(root.left);
        }

        if (root.right != null) {
            parent.put(root.right, root);
            dfs(root.right);
        }
    }


}
